//=========================================================================
// Copyright (C) 2023 The C++ Component Model(COMO) Open Source Project
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//=========================================================================

#include <stdlib.h>
#include <stdbool.h>
#include "Bitmap.h"

#ifdef Bitmap_64
    #define Bitmap_shift        6
    #define Bitmap_mask         63
    #define Bitmap_wordlength   64
    #define Bitmap_allbits_1    (Bitmap_type)0xFFFFFFFFFFFFFFFF
                                             // 7 6 5 4 3 2 1 0
#else   // assumed to be 32 bits
    #define Bitmap_shift        5
    #define Bitmap_mask         31
    #define Bitmap_wordlength   32
    #define Bitmap_allbits_1    (Bitmap_type)0xFFFFFFFF
                                             // 3 2 1 0
#endif

#define Bitmap_ONE        (Bitmap_type)1

/**
 * Set
 */
void Bitmap_Set(Bitmap *b, int n)
{
    if ((0 > n) || (n >= b->bits))
        return;

    int word = n >> Bitmap_shift;     // n / Bitmap_wordlength
    int position = n & Bitmap_mask;   // n % Bitmap_wordlength
    b->array[word] |= Bitmap_ONE << position;
}

/**
 * Clear
 */
void Bitmap_Clear(Bitmap *b, int n)
{
    if ((0 > n) || (n >= b->bits))
        return;

    int word = n >> Bitmap_shift;         // n / Bitmap_wordlength
    int position = n & Bitmap_mask;       // n % Bitmap_wordlength
    b->array[word] &= ~(Bitmap_ONE << position);
}

/**
 * Read
 */
int Bitmap_read(Bitmap *b, int n)
{
    if ((0 > n) || (n >= b->bits))
        return -1;

    int word = n >> Bitmap_shift;         // n / Bitmap_wordlength
    int position = n & Bitmap_mask;       // n % Bitmap_wordlength
    return (b->array[word] >> position) & 1;
}

/**
 * find bit 0, return bit index
 */
int Bitmap_Find(Bitmap *b)
{
    for (int i = 0;  i < b->words;  i++) {
        if (b->array[i] != Bitmap_allbits_1) {
            for (int j = 0;  j < Bitmap_wordlength;  j++) {
                if (((b->array[i] >> j) & 1) == 0) {
                    return i * Bitmap_wordlength + j;
                }
            }
        }
    }

    return -1;
}

/**
 * Allocate
 */
Bitmap *Bitmap_Allocate(int bits, Bitmap_type *array, int array_size)
{
    // divide, but round up for the ceiling
    int words = (bits + Bitmap_wordlength - 1) / Bitmap_wordlength;
    Bitmap *b;

    if (NULL == array) {
        b = malloc(sizeof(Bitmap) + words * sizeof(Bitmap_type));
        if (NULL == b)
            return NULL;
        b->greedy = true;
    }
    else {
        if (array_size < sizeof(Bitmap) + words * sizeof(Bitmap_type))
            return NULL;
        b = (Bitmap *)array;
        b->greedy = false;
    }

    b->bits = bits;
    b->words = words;
    b->array = (Bitmap_type *)((unsigned char *)b + sizeof(Bitmap));

    return b;
}

/**
 * Deallocate
 */
void Bitmap_Deallocate(Bitmap *b)
{
    if (NULL == b)
        return;

    if (b->greedy) {
        free(b);
    }
}
